BZOJ 2231 Garbling Game

Description


Input

输入文件的第一行为3个整数r, c, n. r, c(2<=r, c<=300)是初始矩阵的行数及列数, n (0<=n<10^100)是Pavel进行操作的个数. 接下来的r-1行, 每行包含c-1个字符R, L或N, 代表G矩阵.

Output

输出r*c行, 每行一个整数. 在第i行输出数字i被Pavel写下的次数除以100000之后的余数.

Sample Input

4 5 6
LRLR
NLLR
LNNL

Sample Output

2
0
0
0
0
0
2
1
1
0
0
0
0
0
0
0
0
0
0
0

Solution

首先显然想找循环节,之后的暴力模拟
然而稍微大一点的数据,循环节的长度很可能无法在期望时间内求出,甚至超过了longlong
但是如果把(r-1)(c-1)次打乱作为一个置换
可以直接倍增置换,之后的同样暴力模拟
将置换记为T
首先暴力跑出T,记下置换next[0],以及在i位置被计算的次数cnt[0][i]
需要置换的次数应该是n/(r-1)
(c-1)
注意到数据范围是10^100,做一个高精除低精
然后像快速幂一样一边倍增,一边看是不是要加进答案中去
剩下的暴力
注意取模

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include<bits/stdc++.h>

#define maxn 300+5
#define maxt 100000+5
#define set(a,b) memset(a,(b),sizof(a))

typedef long long ll;

char op[maxn][maxn],s[maxn];
ll T=1,r[maxn],sh[maxn],ls,mod;
int cnt[2][maxt],next[2][maxt];
int res[maxt],st[maxt],number[maxt];
int f[maxn][maxn];
int n,m,k,times,len;

int max(int x,int y)
{

return x>=y ? x : y ;
}

void rot_r(int x,int y)
{

int sup=f[x][y];
f[x][y]=f[x+1][y],f[x+1][y]=f[x+1][y+1],f[x+1][y+1]=f[x][y+1],f[x][y+1]=sup;
}

void rot_l(int x,int y)
{

int sup=f[x][y];
f[x][y]=f[x][y+1],f[x][y+1]=f[x+1][y+1],f[x+1][y+1]=f[x+1][y],f[x+1][y]=sup;
}

void print()
{

for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
printf("%d ",f[i][j]);
}
printf("\n");
}

void mony(int num)
{

for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=(i-1)*m+j;
int x=1,y=1;
while( num-- ){
cnt[0][f[x][y]]++;
if( op[x][y]=='R' )
rot_r(x,y);
else if( op[x][y]=='L' )
rot_l(x,y);
if( y==m-1 ) x=x%(n-1)+1,y=1;
else y++;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
next[0][f[i][j]]=(i-1)*m+j;
}

void divT()
{

T=(n-1)*(m-1);
len=strlen(s);
for(int i=len;i>=1;i--)
r[i]=s[len-i]-'0';
for(int i=len;i>=1;i--){
sh[i]=r[i]/T;
r[i-1]+=r[i]%T*10;
if( !ls && sh[i] ) ls=i;
}
mod=r[0]/10,r[0]=0;
}

void rest(int num)
{

for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=number[(i-1)*m+j];
int x=1,y=1;
while( num-- ){
res[f[x][y]]++;
if( op[x][y]=='R' )
rot_r(x,y);
else if( op[x][y]=='L' )
rot_l(x,y);
if( y==m-1 ) x=x%(n-1)+1,y=1;
else y++;
}
}

void div2()
{

for(int i=ls;i>=1;i--)
sh[i-1]+=sh[i]%2*10,sh[i]/=2;
if( !sh[ls] ) ls--;
}

void DA(int x)
{

for(int i=1;i<=n*m;i++){
cnt[x^1][i]=(cnt[x][i]+cnt[x][next[x][i]])%100000;
next[x^1][i]=next[x][next[x][i]];
}
}

void add(int x)
{

for(int i=1;i<=n*m;i++){
res[i]=(res[i]+cnt[x][st[i]])%100000;
number[next[x][st[i]]]=i,st[i]=next[x][st[i]];
}
}

void QDA()
{

int t=0;
for(int i=1;i<=n*m;i++) st[i]=i;
while( ls ){
if( sh[1]&1 )
add(t);
DA(t),div2(),t^=1;
}
}

void solve()
{

mony((n-1)*(m-1));
divT();
QDA();
rest(mod);
}

int main()
{

scanf("%d%d%s\n",&n,&m,s);
for(int i=1;i<n;i++)
scanf("%s\n",op[i]+1);
solve();
for(int i=1;i<=n*m;i++)
printf("%d\n",res[i]%100000);
return 0;
}